//
//  main.c
//  demo1
//
//  Created by Song on 2018/3/5.
//  Copyright © 2018年 Song. All rights reserved.
//

//  利用链表，进行创建、插入、删除、输出、销毁的操作 （单链表）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct grade {
    int score; // 数据域
    struct grade *next; // 指针域
};

/* 使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，另一个是简化一些比较复杂的类型声明。 */
typedef struct grade node; // typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。

struct grade *creatt(); // 创建链表
void insert(node *head, node *pnew , int i); // 插入链表
void pdelete(node *head, int i); // 删除链表
void display(node *head); // 输出链表
void Pfree(node *head); // 销毁链表

int main(int argc, const char * argv[]) {
    
    node *head,*pnew;
    head = creatt();
    if (head == NULL) {return 0;}
    printf("输出创建的链表：");
    display(head);
    
    // 插入链表
    pnew = (node *)malloc(sizeof(node));
    if (pnew == NULL) {
        printf("创建新链表 pnew 失败");
        return 0;
    }
    pnew->score = 88;
    insert(head, pnew, 4); // 将新节点 插入节点4的后面
    printf("插入后的链表:");
    display(head);
    
    
    // 删除指定链表
    pdelete(head,3);   //删除节点3
    printf("删除后的链表：");
    display(head);
    
    Pfree(head); // 销毁链表
    return 0;
}




// 创建链表
struct grade *creatt() {
    node *head,*tail,*pnew;
    int score; // 输入的分数
    head = (node *)malloc(sizeof(node)); // 创建头结点
    if (head == NULL) {
        printf("创建失败");
        return NULL;
    }
    head->next = NULL; // 头结点 指针域 NULL
    tail = head; // 开始时 尾指针 指向头结点
    printf("输入学生成绩：");
    while (1) { // 创建链表
        scanf("%d",&score);
        if (score < 0) {
            break;
        }
        pnew = (node *)malloc(sizeof(node)); // 创建新节点
        if (pnew == NULL) {
            printf("新节点创建失败");
            return NULL;
        }
        pnew->score = score; // 新节点 数据域 存放输入的成绩
        pnew->next = NULL; // 新节点 指针域 NULL
        tail->next = pnew; // 新节点插入到表尾
        tail = pnew; // 尾指针指向当前的 尾节点
    }
    
    return head; // 返回创建链表的头指针
}

// 插入链表
void insert(node *head, node *pnew, int i) {
    node *p = head; // 当前指针
    
    for (int j = 0; j < i && p != NULL; j++) {
        p = p->next; // p 指向要插入的第i个节点
    }
    if (p == NULL) { // 节点 i 不存在
        printf("插入的节点不存在 - 节点 i 不存在\n");
        return;
    }
    pnew->next = p->next; // 插入节点的指针域指向第i个节点的 后继节点
    p->next = pnew; // 将第i个节点的指针域 指向插入的新节点
}

// 删除链表
void pdelete(node *head, int i) {
    node *p = head, *q;
    if (i == 0) {
        return; // 不可以是头指针
    }
    for (int j = 1; j < i && p->next != NULL; j++) {
        p = p->next; // 将p指向要删除的第i个节点的前驱节点
    }
    if (p->next == NULL) {
        printf("链表中的节点不存在\n");
        return;
    }
    q = p->next;
    p->next = q->next;
    free(q);
}

// 输出链表
void display(node *head) {
    node *p;
    for (p = head->next; p != NULL ; p = p->next) {
        printf("%d ",p->score);
    }
    printf("\n");
}

// 销毁链表
void Pfree(node *head) {
    node *p = head, *q;
    while (p->next != NULL) { // 每次删除头结点的 后继节点
        q = p->next;
        p->next = q->next;
        free(q);
    }
    free(p); // 最后删除头结点
    printf("链表已经销毁\n");
}
